package 中等.脑筋急转弯;

/**
 * 给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
 * 全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
 * 0 <= i < j < n
 * nums[i] > nums[j]
 * 局部倒置 的数目等于满足下述条件的下标 i 的数目：
 * 0 <= i < n - 1
 * nums[i] > nums[i + 1]
 * 当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/global-and-local-inversions
 */
public class 全局倒置与局部倒置_775 {

    public static void main(String[] args) {

        System.out.println(isIdealPermutation(new int[]{0, 2, 3, 1}));

    }

    /**
     * 理解题意
     * 局部倒置的数量等于 nums[i] < nums[i-1] 的数量和
     * 全局倒置的数量等于 nums[i] < nums[0,i-1] 的数量和
     * 如果在索引位置 [0,i-2] 中存在一个数使得 nums[i] < pre2num，那么全局倒置的数量
     * 将会超过局部倒置的数据，返回 false，遍历过程中，需要使得 pre2num 尽可能的大，
     * 来满足这一条件，维护 nums[0,i-2] 中的最大值
     *
     * @param nums
     * @return
     */
    public static boolean isIdealPermutation(int[] nums) {
        int pre2Max = nums[0];

        for (int i = 2; i < nums.length; i++) {
            pre2Max = Math.max(pre2Max, nums[i - 2]);
            if (pre2Max > nums[i]) {
                return false;
            }
        }

        return true;
    }

}
